use std::vec;
use std::ptr::NonNull;
use std::fmt::{Formatter, Display};
use std::marker::PhantomData;
use std::default::Default;
use crate::level_generator::*;

extern crate log;
use log::{trace, error};


//Refactoring: 
//OK > Display pretty print
//OK > impl Drop Trait
//      OK-drop the Node
//      OK-drop the SkipList
//OK  > Random ioslation 
//OK  > Error case handle
//      OK-Error handle 
//      OK-add error log
//OK  > Node name
//  OK > extract struct NodePtr 
//Ok  >remove unsafe in skqiplist struct
//    OK  get() -> Option(&i64) : =>  as_ref<'a>() -> &'a Node ;
//    OK  Iterator -> Lifetime :  => as_ref<'a>() -> &'a Node;
//
//TODO:  
//  for test only > Generic  : interface && type impl [copy & move syntax]
//
//  > module structure ???
//  > Option<NonNull<T>> => NonNull::dangling() as default
//      replace Option<> -> dangling
//      use ref first in mind
//

//safe wrapper for NonNull<Node>
#[derive(Debug, PartialEq, Clone, Copy)]
struct  NodePtr<K> 
where K: Default + PartialOrd + Clone + Copy
{
    ptr: NonNull<Node<K>>,
}

impl <K> NodePtr <K> 
where K: Default + PartialOrd + Clone + Copy
{
    fn from_node(n: Node<K>) -> Self{
        Self {
            ptr: unsafe { NonNull::new_unchecked(Box::into_raw(Box::new(n))) },
        }
    }
    fn to_box_for_autodrop(self) -> Box<Node<K>>{
        unsafe { Box::from_raw(self.ptr.as_ptr()) }
    }
    fn as_ref<'a>(&self) -> &'a Node<K> {
        unsafe { self.ptr.as_ref() }
    }
    fn as_mut<'a>(&mut self) -> &'a mut Node<K> {
        unsafe { self.ptr.as_mut() }
    }
    fn as_ptr(&self) -> *mut Node<K> {
        self.ptr.as_ptr()
    }
}

struct Node<K>
where K: Default + PartialOrd + Clone + Copy
{
    key: K,
    value: i64,
    level: usize, // 0-based
    next: Vec<Option<NodePtr<K>>>,
}

impl <K> Node<K> 
where K: Default + PartialOrd + Clone + Copy
{
    //level 0-based
    fn new(key: K, value: i64, level: usize, next: Option<NodePtr<K>>) -> Self {
        Self { 
            key,
            level,
            value,
            next: vec![next; level+1],
        }
    }

    fn next(&self, i: usize) -> Option<NodePtr<K>> {
        self.next[i]
    }
    fn set_next(&mut self, i: usize, node: Option<NodePtr<K>>) {
        self.next[i] = node;
    }
    fn next_iter_mut(&mut self) -> std::slice::IterMut<'_, Option<NodePtr<K>>> {
        self.next.iter_mut()
    }
    fn to_ptr(&self, mask: usize) -> usize{
       ((self as *const Node<K>) as usize) & mask
    }
}


impl <K> std::fmt::Display for Node<K> 
where K: Default + PartialOrd + Clone + Copy + Display
{
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        write!(f, "k:{:<4}, v:{:<4}, l:{}, &:0x{:04x} next-{}-["
            , self.key, self.value, self.level
            , self.to_ptr(0xffff)
            , self.next.len()
        )?;
        
        for i in 0..SKIP_LIST_MAX_LEVEL {
            if i < self.next.len() {
                let str_ptr = if let Some(ptr) = self.next[i] { 
                    format!("0x{:04x}", (ptr.as_ptr() as usize) & 0xffff)
                } else {
                    "-None-".to_string()
                };
                write!(f, "{}-{} ", i, str_ptr)?;
            }
            else{
                write!(f, "         ")?;
            }
        }
        write!(f, "]")

        /* enumerate() .for each ....
        self.next.iter().enumerate().for_each(|(i, y)| {
            if let Some(ptr) = *y {
                write!(f, "{}-0x{:04x} ", i, ptr.as_ptr() as usize & 0xffff).unwrap();
            } else {
                write!(f, "{}-None ", i).unwrap();
            }
        });
        write!(f, "]")?;
        */
    }
}
impl <K> Drop for Node<K> 
where K: Default + PartialOrd + Clone + Copy
{
    fn drop(&mut self) {
        //trace!("key:{} - Node droped", self.key);
        println!("key:[] - Node droped");
    }
}




const SKIP_LIST_MAX_LEVEL: usize = 6;

struct SkipList<K> 
where K: Default + PartialOrd + Clone + Copy
{
    level: usize,
    header: NodePtr<K>, // non-null && copyable
    tail: NodePtr<K>, //non-null && copyable
    count: usize,
    level_gen: Box<dyn LevelGenerator>,
    _marker: PhantomData<Box<Node<K>>>
}

impl <K> SkipList <K> 
where K: Default + PartialOrd + Clone + Copy
{
    fn new() -> Self{
        let tail = NodePtr::from_node(Node::new(K::default(), 0, SKIP_LIST_MAX_LEVEL - 1, None));
        SkipList{
            level: 0,
            tail,
            header: NodePtr::from_node(Node::new(K::default(), 0, SKIP_LIST_MAX_LEVEL - 1, Some(tail))),
            count: 0,
            level_gen: Box::new(RandomLevelGenerator::new(SKIP_LIST_MAX_LEVEL - 1, 2)),
            //level_gen: Box::new(MockLevelGenerator::new(SKIP_LIST_MAX_LEVEL - 1, vec![0, 1, 2, 3, 4, 5])),
            _marker: PhantomData,
        }
    }

    fn header(&self) -> NodePtr<K> {
        self.header
    }
    fn tail(&self) -> NodePtr<K> {
        self.tail
    }
    fn insert(&mut self, key: K, value: i64) -> Option<i64> {
        let mut prevs: [Option<NodePtr<K>>; SKIP_LIST_MAX_LEVEL] = [None; SKIP_LIST_MAX_LEVEL];
        // find prevs[max_level];
        let mut p = Some(self.header);
        for i in (0..=self.level).rev() {
            while let Some(ref ptr) = p { //ptr: &NodePtr
                if let Some(ref next) =  ptr.as_ref().next(i) { //next: &NodePtr
                    if *next  != self.tail  && next.as_ref().key < key { 
                        p = ptr.as_ref().next(i);
                    }
                    else{
                        break;
                    }
                }
                else{ // p->next(i) is None
                    error!("p->next(i) is None");
                    return None;
                }
            }
            if p.is_none() {
                error!("p is None");
                return None;
            }
            prevs[i] = p;
        }
        //check p:  p->next(i).key ==  key => replace value , ret: Some(old_v)
        if let Some(ref ptr) = p {
            if let Some(ref mut next) = ptr.as_ref().next(0) {
                if next.as_ref().key == key {
                    let v = next.as_ref().value;
                    next.as_mut().value = value;
                    return Some(v);
                } 
                //normal -> key is not equal
            } else {
                error!("p->next is None");
                return None;
            }
        }
        else{
            error!("p is None");
            return None;
        }

        // level = randomLevel;
        let random_level = self.level_gen.next_level(); //0-based
        // random_level >  level =>   prevs(level , random_level] = this_node
        if random_level > self.level {
            for i in self.level + 1..=random_level {
                prevs[i] = Some(self.header);
                self.level += 1;
            }
        }

        //new node
        let mut node = NodePtr::from_node(Node::new(key, value, random_level, None)); 
        // add the prevs[i] -> this_node for [0, level]
        for i in 0..=random_level {
            if let Some(ref mut ptr) = prevs[i] {
                node.as_mut().set_next(i, ptr.as_ref().next(i));
                ptr.as_mut().set_next(i, Some(node));
            }
            else{
                error!("prevs[i:{i}] is None:");
                return None;
            }
        }
        self.count += 1;
        None
    } 

    fn get(&self, key: &K) -> Option<&i64> {
        let mut p = Some(self.header);
        for i in (0..=self.level).rev() {
            while let Some(ref ptr) = p { //NodePtr
                let next_option = ptr.as_ref().next(i); 
                if let Some(ref next) = next_option { //next NodePtr
                    if *next == self.tail {
                        break; 
                    }
                    else{
                        let n =  next.as_ref();//
                        if n.key < *key {
                            p = next_option;
                        }
                        else if n.key == *key {
                            return Some(&n.value);
                        }
                        else{
                            break;
                        }
                    }
                } //if let 
                else{
                    error!("Error! p->next is None");
                }
            }//while let 
            if p.is_none() {
                error!("p is None");
                return None;
            }
        }
        None
    }

    fn remove(&mut self, key: &K) -> Option<i64>{ 
        let mut prevs: [Option<NodePtr<K>>; SKIP_LIST_MAX_LEVEL] = [None; SKIP_LIST_MAX_LEVEL];

        let mut p = Some(self.header);
        for i in (0..=self.level).rev(){
            while let Some(ref prev_ptr)  =  p { //rev_ptr => &NodePtr
                let prev_next = prev_ptr.as_ref().next(i); //Option<NodePtr>
                if let Some(ref next) =  prev_next {
                    if *next != self.tail && next.as_ref().key < *key {
                        p = prev_next;
                    }
                    else{
                        break;
                    }
                } else{
                    error!("p-> next is None, level:[{i}]");
                    return None;
                }
            } // while let
            if p.is_none(){
                error!("leve:[{i}], p is None");
                return None;
            }
            prevs[i] = p;
        }

        if let Some(ref ptr) = p {
            if let Some(ref mut next) = ptr.as_ref().next(0) {
                if *next == self.tail {
                    trace!("not found -- p->next() == tail");
                    return None;
                }
                let next_node = next.as_ref();
                if next_node.key == *key {
                    for i in (0..=next_node.level).rev(){
                        if let Some(ref mut prevs_ptr) = prevs[i] {
                            prevs_ptr.as_mut().set_next(i, next_node.next(i));
                            if prevs_ptr.as_ref().next(i) == Some(self.tail) {
                                self.level -= 1;
                            }
                        }
                        else{
                            error!("previous is None, level:[{i}]"); 
                            return None;
                        }
                    }
                    let v = next_node.value;
                    (*next).to_box_for_autodrop(); //drop it 
                    self.count -= 1;
                    return Some(v);
                }
                //not found 
            } else {
                error!("p->next is None, got an error");
                return None;
            }
        } else {
            error!("p is None, after search node");
            return None;
        }
        None
    }

    fn drop_nodes(&mut self) {
        let mut p = Some(self.header);
        while let Some(ref mut prev) = p {
            if let Some(ref mut next) = prev.as_mut().next(0) {
                if *next != self.tail {
                    prev.as_mut().set_next(0, next.as_ref().next(0));
                    (*next).to_box_for_autodrop();
                    self.count -= 1;
                }
                else{
                    break;
                }
            } else {
                error!("p->next is none");
            }
        }
        if p.is_none() {
            error!("header->next can not be none");
            return ;
        }

        self.header.as_mut()
            .next_iter_mut()
            .for_each(|x| {
                *x = Some(self.tail);
            });
    }

    fn len(&self) -> usize {
        self.count
    }

    fn iter(&self) -> Iter<'_, K> {
        Iter::new(&self)
    }

}//impl SkipList 

struct  Iter<'a, K> 
where K: Default + PartialOrd + Clone + Copy
{
    ptr: NodePtr<K>,
    end: NodePtr<K>,
    marker: PhantomData<&'a Node<K>>
}

impl <'a, K> Iter<'a, K>
where K: Default + PartialOrd + Clone + Copy
{
    fn new(skiplist: &'a SkipList<K> ) -> Self {
        Self {
            ptr: skiplist.header(),
            end: skiplist.tail(),
            marker: PhantomData,
        }
    }
}

use std::iter::Iterator;
impl <'a, K> Iterator for Iter <'a, K> 
where K: Default + PartialOrd + Clone + Copy
{
    type Item = (&'a K, &'a i64);
    fn next(&mut self) -> Option<Self::Item> {
        let next = self.ptr.as_ref().next(0);
        if let Some(next_ptr) = next { //next_ptr is NodePtr
            if next_ptr != self.end {
                let node = next_ptr.as_ref();
                self.ptr = next_ptr;
                return Some((&node.key, &node.value));
            }
        }
        else{
            error!("next is None");
        }
        None
    }
}


impl <K> std::fmt::Display for SkipList<K> 
where K: Default + PartialOrd + Clone + Copy + Display
{

    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        writeln!(f, "max_level:{}, count:{}  ", self.level + 1, self.count)?;
        writeln!(f, "Head:{} ", self.header.as_ref())?;

        writeln!(f, "[ ")?;
        let mut p = self.header.as_ref().next(0);
        while let Some(ref ptr) = p {
            if *ptr != self.tail  {
                writeln!(f, "     {}", ptr.as_ref())?;
                p = ptr.as_ref().next(0);
            }
            else{
                break;
            }

        }
        writeln!(f, "]")?;
        writeln!(f, "Tail:{}", self.tail.as_ref())
    }
}

impl <K> Drop for SkipList<K> 
where K: Default + PartialOrd + Clone + Copy
{
    fn drop(&mut self) {
        self.drop_nodes();
        self.header.to_box_for_autodrop();
        self.tail.to_box_for_autodrop();
        trace!("SkipList droped");
    }
}


#[cfg(test)]
mod test {
    use super::*;
    #[test]
    fn node_test(){ 
        let n = Node::new(1, 1, 0, None);
        println!("node new : {}", n);

        let ptr = NodePtr::from_node(n);
        ptr.to_box_for_autodrop();//drop it 
    }

    #[test]
    fn skiplist_test(){
        let mut sl = SkipList::<i64>::new();
        println!("inited -> {}", sl);
        assert_eq!(0_usize, sl.len());

        let mut records = 0_usize;
        for i in 1..10 {
            assert!(sl.insert(i, i+1).is_none());

            records +=1;
            assert_eq!(records, sl.len());

            assert!(sl.get(&i).is_some());
            assert!(sl.get(&(i+1)).is_none());

            println!("after inserted({},{}) -> {}", i, i+1, sl);
        }

        { //get test 
            assert!(sl.get(&1).is_some());
            assert!(sl.get(&0).is_none());
        }

        { //remove test
            assert!(sl.remove(&100).is_none());
            assert_eq!(records, sl.len());
            println!("remove not-exist key(100) -> {}", sl);

            assert!(sl.remove(&1).is_some());
            records -= 1;
            assert_eq!(records, sl.len());

            println!("removed(1) -> {}", sl);
        }

        { //drop test 
            sl.drop_nodes();
            assert_eq!(0, sl.len());
            println!("drop all nodes -> {}", sl);
        }

    }

    #[test]
    fn iter_test(){
        let mut sl = SkipList::<i64>::new();
        assert!(sl.insert(1, 2).is_none());
        assert!(sl.insert(2, 2).is_none());
        assert!(sl.insert(3, 2).is_none());
        assert!(sl.insert(4, 2).is_none());
        sl.iter().for_each(|x|{
            println!("skiplist: each:{:?}", x);
        });
    }

    #[test]
    fn refactoring_node_fmt(){
        let tail = NodePtr::from_node(Node::new(1, 1, 2, None));
        let header = Node::new(1, 1, 2, Some(tail));

        println!("refactoring head : {}", header);
        println!("refactoring tail : {}", tail.as_ref());

        println!("header:{:p}", &header);
        println!("header:0x{:x}", ((&header as *const Node<i32>) as usize) & 0xffff);
    }


    #[test]
    fn drop_node(){

        { //OK
            let _ = Node::new(1, 1, 2, None);
        }
        {
            let ptr = NodePtr::from_node(Node::new(2, 1, 2, None));
            ptr.to_box_for_autodrop();
        }
    }

    #[test]
    fn drop_skiplist(){
        let _ = SkipList::<i64>::new();
    }
    #[test]
    fn spnodeptr_test(){
        let mut ptr = NodePtr::from_node(Node::new(1, 1, 2, None));
        println!("key:{}", ptr.as_ref().key);
        println!("key:{}", ptr.as_mut().key);
        ptr.to_box_for_autodrop();
    }
/*
*/
}
